from copy import copy

def check(target):
	"""
	Checks whether the given list is sorted.
	>>> print check([])
	True
	>>> print check([1])
	True
	>>> print check([1, 2, 3])
	True
	>>> print check([3, 2, 1])
	False
	>>> print check([76, 97, 38, 59, 84, 10, 74, 33, 75, 23])
	False
	>>> print check([10, 23, 33, 38, 59, 74, 75, 76, 84, 97])
	True
	"""
	for i in range(1, len(target)):
		if target[i-1] > target[i]:
			print >> sys.stderr, "At line", i, "got", target[i-1], "and then", target[i]
			return False
	return True

def sort(target):
	"""
	Sorts numbers using a modified selection sort.
	>>> print check(sort([]))
	True
	>>> print check(sort([1, 2, 3]))
	True
	>>> print check(sort([3, 2, 1]))
	True
	>>> print check(sort([76, 97, 38, 59, 84, 10, 74, 33, 75, 23]))
	True
	"""
	a = copy(target)
	i = 0
	while 2*i < len(a)-1:
		small = big = i
		for j in range(i+1, len(a)-i):
			if a[small] > a[j]: small = j
			if a[big] < a[j]: big = j
		#print "current at", i, "is", a[i]
		#print "small at", small, "is", a[small]
		a[small], a[i] = a[i], a[small]
		if big != i:
			#print "big at", big, "is", a[big]
			a[big], a[len(a)-i-1] = a[len(a)-i-1], a[big]
		#print "got", a
		i += 1
	return a

if __name__ == "__main__":
	import sys
	if len(sys.argv)==2 and sys.argv[1]=="--test":
		import doctest
		doctest.testmod()
	else:
		import os.path
		print >> sys.stderr, "Please enter each number on a separate line and EOF to sort them."
		print >> sys.stderr, "Use %s --test to run unit tests." % os.path.basename(sys.argv[0])
		inp = map(lambda x: int(x), sys.stdin.readlines())
		res = sort(inp)
		print "\n".join(map(lambda x: str(x), res))
		if not check(res):
			print >> sys.stderr, "Consistency check has failed!"
			exit(1)
